package sliding_window;

public class Demo20250322 {
    /**
     * 最小覆盖子串（困难题）！！！
     * @param ss
     * @param tt
     * @return
     */
    public String minWindow(String ss, String tt) {
        // 将 ss,tt 转化为数组
        char[] s = ss.toCharArray();
        char[] t = tt.toCharArray();
        // 保存 t 的字符的个数
        int[] hash1 = new int[128];
        int kinds = 0; // 字符串 t 中有多少种字符
        for (char ch : t) {
            if (hash1[ch] == 0) {
                kinds++;
            }
            hash1[ch]++;
        }
        // 保存窗口中字符的个数
        int[] hash2 = new int[128];
        // minlen 是最小长度，begin 是起始位置
        int minlen = Integer.MAX_VALUE, begin = -1;
        // 滑动窗口的逻辑
        // count 表示字符的种类而不是个数
        for (int left = 0, right = 0, count = 0; right < s.length; right++) {
            // 进窗口，维护 count
            char in = s[right];
            hash2[in]++;
            if (hash2[in] == hash1[in]) {
                count++;
            }
            // 判断
            while (kinds == count) {
                // 更新结果
                if (right - left + 1 < minlen) {
                    begin = left;
                    minlen = right - left + 1;
                }
                // 出窗口，维护 count
                char out = s[left];
                if (hash2[out] == hash1[out]) {
                    count--;
                }
                hash2[out]--;
                left++;
            }
        }
        if (begin == -1) {
            return new String();
        } else {
            return ss.substring(begin, begin + minlen);
        }
    }
}
